package com.gitee.wsl.struct.tree.sample

import com.fleeksoft.charset.internal.assert
import com.gitee.wsl.text.format.format
import kotlin.math.max

/**
 * Implementation of the [AVL tree](https://en.wikipedia.org/wiki/AVL_tree) data
 * structure. **Note:** this tree doesn't use key comparisons, so this tree can't be used as a
 * binary search tree. This implies that the same key can be added to this tree multiple times.
 *
 *
 * AVL tree is a self-balancing binary tree data structure. In an AVL tree, the heights of two child
 * subtrees differ by at most one. This ensures that the height of the tree is $\mathcal{O}(\log n)$
 * where $n$ is the number of elements in the tree. Also this tree doesn't support key comparisons,
 * it does define an element order. As a result, this tree can be used to query node
 * successor/predecessor.
 *
 *
 * Subtree query means that the result is being computed only on the subtree nodes. This tree
 * supports the following operations:
 *
 *  * Min/max insertion and deletion in $\mathcal{O}(\log n)$ time
 *  * Subtree min/max queries in $\mathcal{O}(1)$ time
 *  * Node successor/predecessor queries in $\mathcal{O}(1)$ time
 *  * Tree split in $\mathcal{O}(\log n)$ time
 *  * Tree merge in $\mathcal{O}(\log n)$ time
 *
 *
 *
 * This implementation gives users access to the tree nodes which hold the inserted elements. The
 * user is able to store the tree nodes references but isn't able to modify them.
 *
 * @param <T> the key data type
 * @author Timofey Chudakov
</T> */
class AVLTree<T> : Iterable<T> {
    /**
     * An auxiliary node which's always present in a tree and doesn't contain any data.
     */
    private val virtualRoot = TreeNode<T?>(null)

    /**
     * Modification tracker
     */
    private var modCount = 0

    /**
     * Constructs an empty tree
     */
    constructor()

    /**
     * Constructor for internal usage
     *
     * @param root the root of the newly create tree
     */
    private constructor(root: TreeNode<T?>?) {
        makeRoot(root)
    }

    /**
     * Adds `value` as a maximum element to this tree. The running time of this method is
     * $\mathcal{O}(\log n)$
     *
     * @param value a value to add as a tree max
     * @return a tree node holding the `value`
     */
    fun addMax(value: T): TreeNode<T?> {
        val newMax = TreeNode<T?>(value)
        addMaxNode(newMax)
        return newMax
    }

    /**
     * Adds the `newMax` as a maximum node to this tree.
     *
     * @param newMax a node to add as a tree max
     */
    fun addMaxNode(newMax: TreeNode<T?>?) {
        registerModification()
        if (isEmpty) {
            virtualRoot.left = newMax
            newMax!!.parent = virtualRoot
        } else {
            val max = max
            max!!.setRightChild(newMax)
            balance(max)
        }
    }

    /**
     * Adds the `value` as a minimum element to this tree
     *
     * @param value a value to add as a tree min
     * @return a tree node holding the `value`
     */
    fun addMin(value: T): TreeNode<T?> {
        val newMin = TreeNode<T?>(value)
        addMinNode(newMin)
        return newMin
    }

    /**
     * Adds the `newMin` as a minimum node to this tree
     *
     * @param newMin a node to add as a tree min
     */
    fun addMinNode(newMin: TreeNode<T?>) {
        registerModification()
        if (isEmpty) {
            virtualRoot.left = newMin
            newMin.parent = virtualRoot
        } else {
            val min = min
            min!!.setLeftChild(newMin)
            balance(min)
        }
    }

    /**
     * Splits the tree into two parts.
     *
     *
     * The first part contains the nodes which are smaller than or equal to the `node`. The
     * first part stays in this tree. The second part contains the nodes which are strictly greater
     * than the `node`. The second part is returned as a tree.
     *
     * @param node a separating node
     * @return a tree containing the nodes which are strictly greater than the `node`
     */
    fun splitAfter(node: TreeNode<T?>): AVLTree<T> {
        registerModification()
        val parent = node.parent
        val nextMove = node.isLeftChild
        var left = node.left
        val right = node.right
        node.parent!!.substituteChild(node, null)
        node.reset()
        if (left != null) {
            left.parent = null
        }
        if (right != null) {
            right.parent = null
        }
        if (left == null) {
            left = node
        } else {
            // insert node as a left subtree max
            var t = left
            while (t!!.right != null) {
                t = t.right
            }
            t.setRightChild(node)
            while (t != left) {
                val p = t!!.parent
                p!!.substituteChild(t, balanceNode(t))
                t = p
            }
            left = balanceNode(left)
        }
        return split(left, right, parent, nextMove)
    }

    /**
     * Splits the tree into two parts.
     *
     *
     * The first part contains the nodes which are smaller than the `node`. The first part
     * stays in this tree. The second part contains the nodes which are greater than or equal to the
     * `node`. The second part is returned as a tree.
     *
     * @param node a separating node
     * @return a tree containing the nodes which are greater than or equal to the `node`
     */
    fun splitBefore(node: TreeNode<T?>): AVLTree<T> {
        registerModification()
        val predecessor = predecessor(node)
        if (predecessor == null) {
            // node is a minimum node
            val tree = AVLTree<T>()
            swap(tree)
            return tree
        }
        return splitAfter(predecessor)
    }

    /**
     * Append the nodes in the `tree` after the nodes in this tree.
     *
     *
     * The result of this operation is stored in this tree.
     *
     * @param tree a tree to append
     */
    fun mergeAfter(tree: AVLTree<T>) {
        registerModification()
        if (tree.isEmpty) {
            return
        } else if (tree.size == 1) {
            addMaxNode(tree.removeMin())
            return
        }
        val junctionNode = tree.removeMin()
        val treeRoot = tree.root
        tree.clear()
        makeRoot(merge(junctionNode, this.root, treeRoot))
    }

    /**
     * Prepends the nodes in the `tree` before the nodes in this tree.
     *
     *
     * The result of this operation is stored in this tree.
     *
     * @param tree a tree to prepend
     */
    fun mergeBefore(tree: AVLTree<T>) {
        registerModification()
        tree.mergeAfter(this)
        swap(tree)
    }

    /**
     * Removes the minimum node in this tree. Returns `null` if this tree is empty
     *
     * @return the removed node or `null` if this tree is empty
     */
    fun removeMin(): TreeNode<T?>? {
        registerModification()
        if (isEmpty) {
            return null
        }
        val min = min
        // min.parent != null
        if (min!!.parent === virtualRoot) {
            makeRoot(min!!.right)
        } else {
            min!!.parent!!.setLeftChild(min.right)
        }
        balance(min.parent)
        return min
    }

    /**
     * Removes the maximum node in this tree. Returns `null` if this tree is empty
     *
     * @return the removed node or `null` if this tree is empty
     */
    fun removeMax(): TreeNode<T?>? {
        registerModification()
        if (isEmpty) {
            return null
        }
        val max = max
        if (max!!.parent === virtualRoot) {
            makeRoot(max!!.left)
        } else {
            max!!.parent!!.setRightChild(max.left)
        }
        balance(max.parent)
        return max
    }

    val root: TreeNode<T?>?
        /**
         * Returns the root of this tree or null if this tree is empty.
         *
         * @return the root of this tree or null if this tree is empty.
         */
        get() = virtualRoot.left

    /**
     * Returns the node following the `node` in the order defined by this tree. Returns null
     * if the `node` is the maximum node in the tree.
     *
     * @param node a node to compute successor of
     * @return the successor of the `node`
     */
    fun successor(node: TreeNode<T?>?): TreeNode<T?>? {
        return node!!.successor
    }

    /**
     * Returns the node, which is before the `node` in the order defined by this tree. Returns
     * null if the `node` is the minimum node in the tree.
     *
     * @param node a node to compute predecessor of
     * @return the predecessor of the `node`
     */
    fun predecessor(node: TreeNode<T?>): TreeNode<T?>? {
        return node.predecessor
    }

    val min: TreeNode<T?>?
        /**
         * Returns the minimum node in this tree or null if the tree is empty.
         *
         * @return the minimum node in this tree or null if the tree is empty.
         */
        get() = if (this.root == null) null else this.root!!.subtreeMin
    val max: TreeNode<T?>?
        /**
         * Returns the maximum node in this tree or null if the tree is empty.
         *
         * @return the maximum node in this tree or null if the tree is empty.
         */
        get() = if (this.root == null) null else this.root!!.subtreeMax
    val isEmpty: Boolean
        /**
         * Check if this tree is empty
         *
         * @return `true` if this tree is empty, `false otherwise`
         */
        get() = this.root == null

    /**
     * Removes all nodes from this tree.
     *
     *
     * **Note:** the memory allocated for the tree structure won't be deallocated until there are
     * active external referenced to the nodes of this tree.
     */
    fun clear() {
        registerModification()
        virtualRoot.left = null
    }

    val size: Int
        /**
         * Returns the size of this tree
         *
         * @return the size of this tree
         */
        get() = if (virtualRoot.left == null) 0 else virtualRoot.left!!.subtreeSize

    /**
     * Makes the `node` the root of this tree
     *
     * @param node a new root of this tree
     */
    private fun makeRoot(node: TreeNode<T?>?) {
        virtualRoot.left = node
        if (node != null) {
            node.subtreeMax!!.successor = null
            node.subtreeMin!!.predecessor = null
            node.parent = virtualRoot
        }
    }

    /**
     * Traverses the tree up until the virtual root and splits it into two parts.
     *
     *
     * The algorithm is described in *Donald E. Knuth. The art of computer programming. Second
     * Edition. Volume 3 / Sorting and Searching, p. 474*.
     *
     * @param left a left subtree
     * @param right a right subtree
     * @param p next parent node
     * @param leftMove `true` if we're moving from the left child, `false` otherwise.
     * @return the resulting right tree
     */
    private fun split(left: TreeNode<T?>?, right: TreeNode<T?>?, p: TreeNode<T?>?, leftMove: Boolean): AVLTree<T> {
        var left = left
        var right = right
        var p = p
        var leftMove = leftMove
        while (p !== virtualRoot) {
            val nextMove = p!!.isLeftChild
            val nextP = p.parent
            p.parent!!.substituteChild(p, null)
            p.parent = null
            if (leftMove) {
                right = merge(p, right, p.right)
            } else {
                left = merge(p, p.left, left)
            }
            p = nextP
            leftMove = nextMove
        }
        makeRoot(left)
        return AVLTree(right)
    }

    /**
     * Merges the `left` and `right` subtrees using the `junctionNode`.
     *
     *
     * The algorithm is described in *Donald E. Knuth. The art of computer programming. Second
     * Edition. Volume 3 / Sorting and Searching, p. 474*.
     *
     * @param junctionNode a node between left and right subtrees
     * @param left a left subtree
     * @param right a right subtree
     * @return the root of the resulting tree
     */
    private fun merge(junctionNode: TreeNode<T?>?, left: TreeNode<T?>?, right: TreeNode<T?>?): TreeNode<T?>? {
        return if (left == null && right == null) {
            junctionNode!!.reset()
            junctionNode
        } else if (left == null) {
            right!!.setLeftChild(merge(junctionNode, null, right.left))
            balanceNode(right)
        } else if (right == null) {
            left.setRightChild(merge(junctionNode, left.right, right))
            balanceNode(left)
        } else if (left.height > right.height + 1) {
            left.setRightChild(merge(junctionNode, left.right, right))
            balanceNode(left)
        } else if (right.height > left.height + 1) {
            right.setLeftChild(merge(junctionNode, left, right.left))
            balanceNode(right)
        } else {
            junctionNode!!.setLeftChild(left)
            junctionNode.setRightChild(right)
            balanceNode(junctionNode)
        }
    }

    /**
     * Swaps the contents of this tree and the `tree`
     *
     * @param tree a tree to swap content of
     */
    private fun swap(tree: AVLTree<T>) {
        val t = virtualRoot.left
        makeRoot(tree.virtualRoot.left)
        tree.makeRoot(t)
    }

    /**
     * Performs a right node rotation.
     *
     * @param node a node to rotate
     * @return a new parent of the `node`
     */
    private fun rotateRight(node: TreeNode<T?>): TreeNode<T?> {
        val left = node.left
        left!!.parent = null
        node.setLeftChild(left.right)
        left.setRightChild(node)
        node.updateHeightAndSubtreeSize()
        left.updateHeightAndSubtreeSize()
        return left
    }

    /**
     * Performs a left node rotation.
     *
     * @param node a node to rotate
     * @return a new parent of the `node`
     */
    private fun rotateLeft(node: TreeNode<T?>): TreeNode<T?> {
        val right = node.right
        right!!.parent = null
        node.setRightChild(right.left)
        right.setLeftChild(node)
        node.updateHeightAndSubtreeSize()
        right.updateHeightAndSubtreeSize()
        return right
    }
    /**
     * Performs a node balancing on the path from `node` up until the `stop` node
     *
     * @param node a node to start tree balancing from
     * @param stop a node to stop balancing at (this node is not being balanced)
     */
    /**
     * Performs a node balancing on the path from `node` up until the root
     *
     * @param node a node to start tree balancing from
     */
    private fun balance(node: TreeNode<T?>?, stop: TreeNode<T?> = virtualRoot) {
        if (node === stop) {
            return
        }
        val p = node!!.parent
        if (p === virtualRoot) {
            makeRoot(balanceNode(node))
        } else {
            p!!.substituteChild(node, balanceNode(node))
        }
        balance(p, stop)
    }

    /**
     * Checks whether the `node` is unbalanced. If so, balances the `node`
     *
     * @param node a node to balance
     * @return a new parent of `node` if the balancing occurs, `node` otherwise
     */
    private fun balanceNode(node: TreeNode<T?>): TreeNode<T?>? {
        node.updateHeightAndSubtreeSize()
        if (node.isLeftDoubleHeavy) {
            if (node.left!!.isRightHeavy) {
                node.setLeftChild(rotateLeft(node.left!!))
            }
            rotateRight(node)
            return node.parent
        } else if (node.isRightDoubleHeavy) {
            if (node.right!!.isLeftHeavy) {
                node.setRightChild(rotateRight(node.right!!))
            }
            rotateLeft(node)
            return node.parent
        }
        return node
    }

    /**
     * Registers a modifying operation
     */
    private fun registerModification() {
        ++modCount
    }

    /**
     * {@inheritDoc}
     */
    override fun toString(): String {
        val builder = StringBuilder()
        val i = nodeIterator()
        while (i.hasNext()) {
            val node = i.next()
            builder.append(node.toString()).append("\n")
        }
        return builder.toString()
    }

    /**
     * {@inheritDoc}
     */
    override fun iterator(): MutableIterator<T> {
        return TreeValuesIterator()
    }

    /**
     * Returns an iterator over the tree nodes rather than the node values. The tree are returned in
     * the same order as the tree values.
     *
     * @return an iterator over the tree nodes
     */
    fun nodeIterator(): Iterator<TreeNode<T?>> {
        return TreeNodeIterator()
    }

    /**
     * Iterator over the values stored in this tree. This implementation uses the
     * `TreeNodeIterator` to iterator over the values.
     */
    private inner class TreeValuesIterator : MutableIterator<T> {
        /**
         * Internally used `TreeNodeIterator`
         */
        private val iterator: TreeNodeIterator = TreeNodeIterator()

        /**
         * {@inheritDoc}
         */
        override fun hasNext(): Boolean {
            return iterator.hasNext()
        }

        /**
         * {@inheritDoc}
         */
        override fun next(): T {
            return iterator.next()!!.value!!
        }

        override fun remove() {
            TODO("Not yet implemented")
        }
    }

    /**
     * Iterator over the tree nodes. The nodes are returned according to the in order tree
     * traversal.
     */
    private inner class TreeNodeIterator : MutableIterator<TreeNode<T?>> {
        /**
         * A node that is returned next or `null` if all nodes are traversed
         */
        private var nextNode: TreeNode<T?>?

        /**
         * Number of modifications of the tree at the time this iterator is created.
         */
        private val expectedModCount: Int

        /**
         * Constructs a new `TreeNodeIterator`
         */
        init {
            nextNode = min
            expectedModCount = modCount
        }

        /**
         * {@inheritDoc}
         */
        override fun hasNext(): Boolean {
            checkForComodification()
            return nextNode != null
        }

        /**
         * {@inheritDoc}
         */
        override fun next(): TreeNode<T?> {
            if (!hasNext()) {
                throw NoSuchElementException()
            }
            val result = nextNode
            nextNode = successor(nextNode)
            return result!!
        }

        override fun remove() {
            TODO("Not yet implemented")
        }

        /**
         * Checks if the tree has been modified during the iteration process
         */
        private fun checkForComodification() {
            if (expectedModCount != modCount) {
                throw ConcurrentModificationException()
            }
        }
    }

    /**
     * Container holding the values stored in the tree.
     *
     * @param <T> a tree node value type
    </T> */
    class TreeNode<T> internal constructor(
        /**
         * A value stored in this tree node
         */
        var value: T
    ) {
        /**
         * Returns a value stored in this node
         *
         * @return a value stored in this node
         */
        /**
         * Returns a parent of this node
         *
         * @return a parent of this node
         */
        /**
         * Parent of this node
         */
        var parent: TreeNode<T>? = null
        /**
         * Returns a left child of this node
         *
         * @return a left child of this node
         */
        /**
         * Left child of this node
         */
        var left: TreeNode<T>? = null
        /**
         * Returns a right child of this node
         *
         * @return a right child of this node
         */
        /**
         * Right child of this node
         */
        var right: TreeNode<T>? = null

        /**
         * Next node in the tree according to the in order traversal
         */
        var successor: TreeNode<T>? = null

        /**
         * Previous node in the tree according to the in order traversal
         */
        var predecessor: TreeNode<T>? = null
        /**
         * Returns a minimum node stored in the subtree rooted at this node
         *
         * @return a minimum node stored in the subtree rooted at this node
         */
        /**
         * A minimum node in the subtree rooted at this node
         */
        var subtreeMin: TreeNode<T>? = null
        /**
         * Returns a maximum node stored in the subtree rooted at this node
         *
         * @return a maximum node stored in the subtree rooted at this node
         */
        /**
         * A maximum node in the subtree rooted at this node
         */
        var subtreeMax: TreeNode<T>? = null
        /**
         * Returns a height of this node
         *
         * @return a height of this node
         */
        /**
         * Height of the node
         */
        var height = 0
        /**
         * Returns a subtree size of the tree rooted at this node
         *
         * @return a subtree size of the tree rooted at this node
         */
        /**
         * Size of the subtree rooted at this node
         */
        var subtreeSize = 0

        /**
         * Constructs a new node with the `value` stored in it
         *
         * @param value a value to store in this node
         */
        init {
            reset()
        }

        val root: TreeNode<T>?
            /**
             * Returns a root of the tree this node is stored in
             *
             * @return a root of the tree this node is stored in
             */
            get() {
                var current: TreeNode<T>? = this
                while (current!!.parent != null) {
                    current = current.parent
                }
                return current.left
            }
        val treeMin: TreeNode<T>?
            /**
             * Returns a minimum node stored in the tree
             *
             * @return a minimum node stored in the tree
             */
            get() = this.root!!.subtreeMin
        val treeMax: TreeNode<T>?
            /**
             * Returns a maximum node stored in the tree
             *
             * @return a maximum node stored in the tree
             */
            get() = this.root!!.subtreeMax

        /**
         * Resets this node to the default state
         */
        fun reset() {
            height = 1
            subtreeSize = 1
            subtreeMin = this
            subtreeMax = this
            successor = null
            predecessor = null
            parent = null
            right = null
            left = null
        }

        val rightHeight: Int
            /**
             * Returns a height of the right subtree
             *
             * @return a height of the right subtree
             */
            get() = if (right == null) 0 else right!!.height
        val leftHeight: Int
            /**
             * Returns a height of the left subtree
             *
             * @return a height of the right subtree
             */
            get() = if (left == null) 0 else left!!.height
        val leftSubtreeSize: Int
            /**
             * Returns a size of the left subtree
             *
             * @return a size of the left subtree
             */
            get() = if (left == null) 0 else left!!.subtreeSize
        val rightSubtreeSize: Int
            /**
             * Returns a size of the right subtree
             *
             * @return a size of the right subtree
             */
            get() = if (right == null) 0 else right!!.subtreeSize

        /**
         * Updates the height and subtree size of this node according to the values of the left and
         * right children
         */
        fun updateHeightAndSubtreeSize() {
            height = max(leftHeight, rightHeight) + 1
            subtreeSize = leftSubtreeSize + rightSubtreeSize + 1
        }

        val isLeftDoubleHeavy: Boolean
            /**
             * Returns `true` if this node is unbalanced and the left child's height is greater,
             * `false otherwise`
             *
             * @return `true` if this node is unbalanced and the left child's height is greater,
             * `false otherwise`
             */
            get() = leftHeight > rightHeight + 1
        val isRightDoubleHeavy: Boolean
            /**
             * Returns `true` if this node is unbalanced and the right child's height is greater,
             * `false otherwise`
             *
             * @return `true` if this node is unbalanced and the right child's height is greater,
             * `false otherwise`
             */
            get() = rightHeight > leftHeight + 1
        val isLeftHeavy: Boolean
            /**
             * Returns `true` if the height of the left child is greater than the height of the
             * right child
             *
             * @return `true` if the height of the left child is greater than the height of the
             * right child
             */
            get() = leftHeight > rightHeight
        val isRightHeavy: Boolean
            /**
             * Returns `true` if the height of the right child is greater than the height of the
             * left child
             *
             * @return `true` if the height of the right child is greater than the height of the
             * left child
             */
            get() = rightHeight > leftHeight
        val isLeftChild: Boolean
            /**
             * Returns `true` if this node is a left child of its parent, `false` otherwise
             *
             * @return `true` if this node is a left child of its parent, `false` otherwise
             */
            get() = this === parent!!.left
        val isRightChild: Boolean
            /**
             * Returns `true` if this node is a right child of its parent, `false` otherwise
             *
             * @return `true` if this node is a right child of its parent, `false` otherwise
             */
            get() = this === parent!!.right

        /**
         * Returns a successor of this node according to the tree in order traversal, or
         * `null` if this node is a maximum node in the tree
         *
         * @return successor of this node, or `` null if this node in a maximum node in the
         * tree
         */
        /*fun getSuccessor(): TreeNode<T>? {
            return successor
        }*/

        /**
         * Returns a predecessor of this node according to the tree in order traversal, or
         * `null` if this node is a minimum node in the tree
         *
         * @return predecessor of this node, or `` null if this node in a minimum node in the
         * tree
         */
        /*fun getPredecessor(): TreeNode<T>? {
            return predecessor
        }*/

        /**
         * Updates the successor reference of this node. If the `node` is not `null`,
         * updates its predecessor reference as well
         *
         * @param node new successor
         */
        private fun _setSuccessor(node: TreeNode<T>?) {
            successor = node
            if (node != null) {
                node.predecessor = this
            }
        }

        /**
         * Updates the predecessor reference of this node. If the `node` is not `null`,
         * updates its successor reference as well
         *
         * @param node new predecessor
         */
        private fun _setPredecessor(node: TreeNode<T>?) {
            predecessor = node
            if (node != null) {
                node.successor = this
            }
        }

        /**
         * Sets the left child reference of this node to `node`. If the `node` is not
         * `null`, updates its parent reference as well.
         *
         * @param node a new left child
         */
        fun setLeftChild(node: TreeNode<T>?) {
            left = node
            if (node != null) {
                node.parent = this
                _setPredecessor(node.subtreeMax)
                subtreeMin = node.subtreeMin
            } else {
                subtreeMin = this
                predecessor = null
            }
        }

        /**
         * Sets the right child reference of this node to `node`. If the `node` is not
         * `null`, updates its parent reference as well.
         *
         * @param node a new right child
         */
        fun setRightChild(node: TreeNode<T>?) {
            right = node
            if (node != null) {
                node.parent = this
                _setSuccessor(node.subtreeMin)
                subtreeMax = node.subtreeMax
            } else {
                successor = null
                subtreeMax = this
            }
        }

        /**
         * Substitutes the `prevChild` with the `newChild`. If the `newChild` is
         * not `null`, updates its parent reference as well
         *
         * @param prevChild either left or right child of this node
         * @param newChild a new child of this node
         */
        fun substituteChild(prevChild: TreeNode<T>, newChild: TreeNode<T>?) {
            assert(left === prevChild || right === prevChild)
            assert(!(left === prevChild && right === prevChild))
            if (left === prevChild) {
                setLeftChild(newChild)
            } else {
                setRightChild(newChild)
            }
        }

        /**
         * {@inheritDoc}
         */
        override fun toString(): String {
            return String.format(
                "{%s}: [parent = %s, left = %s, right = %s], [subtreeMin = %s, subtreeMax = %s], [predecessor = %s, successor = %s], [height = %d, subtreeSize = %d]",
                value, if (parent == null) "null" else parent!!.value, if (left == null) "null" else left!!.value,
                if (right == null) "null" else right!!.value,
                if (subtreeMin == null) "null" else subtreeMin!!.value,
                if (subtreeMax == null) "null" else subtreeMax!!.value,
                if (predecessor == null) "null" else predecessor!!.value,
                if (successor == null) "null" else successor!!.value, height, subtreeSize
            )
        }
    }
}
